{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #点名"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表 #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: takeAttendance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #点名"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 <code>records</code>。假定仅有一位同学缺席，请返回他的学号。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> records = [0,1,2,3,5]\n",
    "<strong>输出:</strong> 4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> records = [0, 1, 2, 3, 4, 5, 6, 8]\n",
    "<strong>输出:</strong> 7</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<p><code>1 &lt;= records.length&nbsp;&lt;= 10000</code></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [que-shi-de-shu-zi-lcof](https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [que-shi-de-shu-zi-lcof](https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(records) - 1\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if records[mid] == mid:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        for i in range(len(records)):\n",
    "            if i != records[i]:\n",
    "                return i\n",
    "        return len(records)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        n = len(records)\n",
    "        s1 = (0+n) * (n+1) / 2\n",
    "        s2 = sum(records)\n",
    "        return int(s1 - s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        i,j = 0,len(records)-1\n",
    "\n",
    "        while i<=j:\n",
    "            m = (i+j) // 2\n",
    "            if records[m] == m:i=m+1\n",
    "            else:j=m-1\n",
    "    \n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        if records[-1] == len(records)-1:\n",
    "            return records[-1]+1\n",
    "        left, right = 0, len(records)-1\n",
    "        while left < right:\n",
    "            mid = (left+right) // 2\n",
    "            if records[mid] != mid:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i!=nums[i]:return i\n",
    "        return nums[-1]+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        for i in range(len(records)):\n",
    "            if i != records[i]: return i\n",
    "        return len(records)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        i,j = 0,len(records)-1\n",
    "        while i <= j:\n",
    "            m = (i+j)//2\n",
    "            if records[m] == m:\n",
    "                i = m+1\n",
    "            else:\n",
    "                j = m-1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        left, right = 0, len(records)-1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if records[mid] == mid:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        return sum(range(0, len(records) + 1)) - sum(records)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        for i in range(len(records)):\n",
    "            if records[i] != i :\n",
    "                return i\n",
    "        return len(records)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        x=0\n",
    "        y=len(records)-1\n",
    "        while x<=y:\n",
    "            m=(x+y)//2\n",
    "            if  m==records[m]:\n",
    "                x=m+1\n",
    "            else:\n",
    "                y=m-1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        s, e  = 0, len(records)\n",
    "        while s<e:\n",
    "            mid = (s+e)//2\n",
    "            if records[mid]==mid:\n",
    "                s = mid + 1\n",
    "            else:\n",
    "                e = mid\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        n = len(records)\n",
    "        if records[-1] == n-1:\n",
    "            return n\n",
    "\n",
    "        left, right = 0, n-1\n",
    "        while left < right - 1:\n",
    "            mid = (left+right) // 2\n",
    "            if records[mid] == mid:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        if records[left] != left:\n",
    "            return left\n",
    "        else:\n",
    "            return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        length=records[-1]\n",
    "        if records[0] !=0:\n",
    "            return 0\n",
    "        num=sum(range(length+1))-sum(records)\n",
    "        if num:\n",
    "            return num\n",
    "        else:\n",
    "            return length+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        for i in range(len(records)):\n",
    "           if i!=records[i]:\n",
    "                return i\n",
    "        return len(records)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        i=0\n",
    "        for i in range(len(records)):\n",
    "            if i!=records[i]:\n",
    "                return i\n",
    "        return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        lst=[0]*(len(records)+1)\n",
    "        for i in records:\n",
    "            lst[i]=1\n",
    "        for i in range(len(lst)):\n",
    "            if lst[i]==0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        n=-2\n",
    "        for i in records:\n",
    "            n=n+1\n",
    "            if i!=n+1:\n",
    "                return n+1\n",
    "        return n+2\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = len(records)\n",
    "        while l < r:\n",
    "            mid = l + (r-l) // 2\n",
    "            if records[mid] == mid:\n",
    "                l = mid + 1\n",
    "            elif records[mid] > mid:\n",
    "                r = mid\n",
    "        return l\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        return len(records) * (len(records)+1) //2 - sum(records)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        left, right = 0, len(records) - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if records[mid] == mid:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        if records[-1] == len(records)-1:\n",
    "            return records[-1]+1\n",
    "        left, right = 0, len(records)-1\n",
    "        while left < right:\n",
    "            mid = (left+right) // 2\n",
    "            if records[mid] != mid:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        i, j = 0, len(records)-1\n",
    "        while i <= j:\n",
    "            n = (i+j)//2\n",
    "            if n == records[n]: i = n+1\n",
    "            if n != records[n]: j -= 1\n",
    "        return j+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        i=0\n",
    "        j=len(records)-1\n",
    "        while i<=j:\n",
    "            m=(i+j)//2\n",
    "            if m==records[m]:\n",
    "                i=m+1\n",
    "            else:\n",
    "                j=m-1\n",
    "        \n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        if records[0] != 0:\n",
    "            return 0\n",
    "        i,j = 0,len(records)-1\n",
    "        while i<=j:\n",
    "            m = i+(j-i)//2\n",
    "            if records[m] == m:\n",
    "                i = m+1\n",
    "            else:\n",
    "                j = m-1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        if records[len(records)-1]==len(records)-1: return len(records)\n",
    "        for i in range(len(records)):\n",
    "            if records[i]!=i:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        a, b = 0, len(records)-1\n",
    "        while a <= b:\n",
    "            index = (a+b) // 2\n",
    "            if records[index] == index:\n",
    "                a = index + 1\n",
    "            else:\n",
    "                b = index - 1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        for i in range(len(records)):\n",
    "            if records[i] != i:\n",
    "                return i\n",
    "        return len(records)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        # n = len(records)\n",
    "        # sum = ((0 + n) * (n + 1)) // 2\n",
    "        # for i in records:\n",
    "        #     sum -= i\n",
    "\n",
    "        # return sum\n",
    "\n",
    "        i, j = 0, len(records) - 1\n",
    "        while i <= j:\n",
    "            m = (i + j) // 2\n",
    "            if records[m] == m: i = m + 1\n",
    "            elif records[m] != m:\n",
    "                j = m - 1\n",
    "        \n",
    "        return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        l , r = 0, len(records)-1\n",
    "        while l <= r:\n",
    "            mid = (l+r)//2\n",
    "            if records[mid] == mid:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        for i in range(len(records)):\n",
    "            if i!=records[i]:\n",
    "                return i\n",
    "        return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        i = 0\n",
    "        while i < len(records) and i == records[i]:\n",
    "            i+=1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        i, j = 0, len(records)-1\n",
    "        while i <= j:\n",
    "            n = (i+j)//2\n",
    "            if n == records[n]: i = n+1\n",
    "            if n != records[n]: j = n-1\n",
    "        return j+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        i, j = 0, len(records)-1\n",
    "        while i <= j:\n",
    "            n = (i+j)//2\n",
    "            if n == records[n]: i = n+1\n",
    "            if n != records[n]: j = n-1\n",
    "        return j+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        i, j = 0, 1\n",
    "        if(records[0] == 1):\n",
    "            return 0\n",
    "        while(j < len(records)):\n",
    "            if(records[j] - records[i] > 1):\n",
    "                return records[i] + 1\n",
    "                break\n",
    "            i += 1\n",
    "            j += 1\n",
    "        return records[-1] + 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        return sum(range(len(records)+1))-sum(records)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        if not records: return\n",
    "        i, j = 0, len(records) - 1\n",
    "        while i <= j:\n",
    "            m = (i + j) // 2\n",
    "            print(i, j, m)\n",
    "            if records[m] > m: j = m - 1\n",
    "            else: i = m + 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        if len(records)==0:\n",
    "            return 0\n",
    "        # elif len(records)==1:\n",
    "        #     if records[0] ==1:\n",
    "        #         return 0\n",
    "        #     else:\n",
    "        #         return 1\n",
    "        else:\n",
    "            for i, x in enumerate(records):\n",
    "                if i != x:\n",
    "                    return i\n",
    "            return x+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        i, j = 0, len(records)-1\n",
    "        while i <= j:\n",
    "            n = (i+j)//2\n",
    "            if n == records[n]: i = n+1\n",
    "            if n != records[n]: j -= 1\n",
    "        return j+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records):\n",
    "        for index, key in enumerate(records):\n",
    "            if index != key:\n",
    "                return index\n",
    "                break\n",
    "        return len(records)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        if not records: return\n",
    "        i, j = 0, len(records) - 1\n",
    "        while i <= j:\n",
    "            m = (i + j) // 2\n",
    "            print(i, j, m)\n",
    "            #if j == len(records): return len(records)\n",
    "            if records[m] > m: j = m - 1\n",
    "            else: i = m + 1\n",
    "        return j + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        total_sum=len(records)*(len(records)+1)*0.5\n",
    "        return int(total_sum-sum(records))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        n = len(records) + 1\n",
    "        sum_value = (n-1)*n//2\n",
    "        all_value = sum(records)\n",
    "        delta = sum_value - all_value\n",
    "        return delta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        n = records[-1]\n",
    "        for i in range(n+2):\n",
    "            if i not in records:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        low,high = 0,len(records)\n",
    "        mid = -1\n",
    "        while low<high:\n",
    "            mid = (low+high)//2\n",
    "            if records[mid] == mid:\n",
    "                low = mid+1\n",
    "            else:\n",
    "                high = mid-1\n",
    "        if low == len(records):\n",
    "            return len(records)\n",
    "        elif records[low] == low:\n",
    "            return records[low]+1\n",
    "        else:\n",
    "            return records[low]-1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, nums: List[int]) -> int:\n",
    "       \n",
    "        if nums[0]!=0:\n",
    "            return 0\n",
    "        if nums[-1] == len(nums)-1:\n",
    "            return len(nums)\n",
    "\n",
    "        l = 0\n",
    "        r = len(nums)-1\n",
    "        res = 0\n",
    "        while l<=r:\n",
    "            mid = l+(r-l)//2\n",
    "            if nums[mid-1] == mid-1 and nums[mid] != mid:\n",
    "                res = mid+1\n",
    "                break\n",
    "            if nums[mid] == mid+1:\n",
    "                r = mid-1\n",
    "            if nums[mid] == mid:\n",
    "                l = mid+1\n",
    "        return res-1    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        num=0\n",
    "        for i in records:\n",
    "            print(i,num)\n",
    "            if i<=num and i==records[i]:\n",
    "                num+=1\n",
    "           # else:\n",
    "             #   break\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        num=0\n",
    "        for i in records:\n",
    "            print(i,num)\n",
    "            if i<=num and i==records[i]:\n",
    "                num+=1\n",
    "           # else:\n",
    "             #   break\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        # for i in range(len(records) - 1):\n",
    "        #     if records[i + 1] - records[i] != 1:\n",
    "        #         return records[i] + 1\n",
    "        res = []\n",
    "        for i in range(len(records) + 1):\n",
    "            res.append(i)\n",
    "        print(sum(records))\n",
    "        print(sum(res))\n",
    "        return sum(res) - sum(records)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeAttendance(self, records: List[int]) -> int:\n",
    "        if not records: return\n",
    "        i, j = 0, len(records) - 1\n",
    "        while i <= j:\n",
    "            m = (i + j) // 2\n",
    "            print(i, j, m)\n",
    "            if records[m] > m: j = m - 1\n",
    "            else: i = m + 1\n",
    "        return j + 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
